package com.emeraldparser.util;

import java.util.Collection;
import java.util.Collections;
import java.util.Deque;
import java.util.Set;

import com.google.common.collect.Lists;
import com.google.common.collect.Sets;

public class DepthFirstVisitor<V, E> {

	private final Graph<V, E> graph;
	private final transient Set<V> unvisitedVertices;
	private final transient Deque<Graph.Edge<V, E>> currentPath = Lists.newLinkedList();

	public DepthFirstVisitor(Graph<V, E> graph) {
		this.graph = graph;
		this.unvisitedVertices = Sets.newHashSet(graph.vertices());
	}

	public static <V, E> DepthFirstVisitor<V, E> create(Graph<V, E> graph) {
		return new DepthFirstVisitor<V, E>(graph);
	}

	public void visit() {
		while (!unvisitedVertices.isEmpty()) {
			V vertex = unvisitedVertices.iterator().next();
			visit(vertex);
		}
	}

	public void visit(V vertex) {
		if (!isVisited(vertex)) {
			setVisited(vertex, true);
			visitSuccessors(vertex);
		}
	}

	/**
	 * Returns <code>true</code> if the vertex has been previously visited.
	 * 
	 * @param vertex
	 * @return
	 */
	public boolean isVisited(V vertex) {
		return !unvisitedVertices.contains(vertex);
	}

	public void setVisited(V vertex, boolean visited) {
		if (visited) {
			unvisitedVertices.remove(vertex);
		} else {
			unvisitedVertices.add(vertex);
		}
	}

	public void visitSuccessors(V vertex) {
		for (Graph.Edge<V, E> edge : graph.outboundEdges(vertex)) {
			currentPath.addLast(edge);
			try {
				visit(edge.getDestination());
			} finally {
				currentPath.removeLast();
			}
		}
	}

	protected Collection<Graph.Edge<V, E>> getPath() {
		return Collections.unmodifiableCollection(currentPath);
	}

}
